/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/encode-string-with-shortest-length
   @Language: C++
   @Datetime: 19-05-09 16:03
   */

class Solution {
public:
	/**
	 * @param s: a string
	 * @return: return a string
	 */
	string encode(string &s) {
		// write your code here
		int n=s.length();
		vector<vector<string> > dp(n,vector<string>(n));
		for(int len=1; len<=n; ++len){
			for(int i=0; i+len<=n; ++i){
				int j=i+len-1;
				string tmp=dp[i][j]=s.substr(i,len);
				int pos=(tmp+tmp).find(tmp,1);
				if(pos<tmp.length()){
					string replace=to_string(tmp.length()/pos)+"["+dp[i][i+pos-1]+"]";
					if(replace.length()<dp[i][j].length()) dp[i][j]=replace;
					continue;
				}
				for(int k=i; k<j; ++k){
					if(dp[i][k].length()+dp[k+1][j].length()<dp[i][j].length())
						dp[i][j]=dp[i][k]+dp[k+1][j];
				}
			}
		}
		return dp[0][n-1];
	}
};
